perm filename 4R.DOC[HAL,HE] blob
sn#113513 filedate 1974-07-28 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00026 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00003 00002 FORWARD
C00004 00003 INTRODUCTION
C00010 00004 GOALS
C00017 00005 THE RUNTIME SYSTEM
C00027 00006 A SAMPLE DIALOG WITH THE HAL SYSTEM
C00035 00007 GENERAL OUTLINE OF THE HAL SYSTEM
C00048 00008 OVERVIEW OF THE HAL SOURCE LANGUAGE
C00049 00009 CONTROL STRUCTURES
C00053 00010 ON MONITORS
C00062 00011 DATA STRUCTURES
C00066 00012 ALGEBRAIC DATATYPES
C00075 00013 ARITHMETIC
C00080 00014 SOME EXAMPLES OF ARITHMETIC EXPRESSIONS
C00081 00015 MOTION SPECIFICATIONS
C00090 00016 OPTIONS FOR MOVES
C00098 00017 COMPLEX MOVES
C00102 00018 SEARCHES
C00107 00019 DEVICE CONTROL
C00112 00020 WORLD MODEL SPECIFICATION
C00123 00021 USES OF THE WORLD MODEL
C00125 00022 OVERVIEW OF THE RUNTIME
C00126 00023 CONTROL STRUCTURES
C00133 00024 INTERPRETABLE CODE
C00142 00025 DATA STRUCTURES
C00149 00026 TRAJECTORIES not yet ready for perusal
C00176 ENDMK
C⊗;
FORWARD
This document describes the new hand language, HAL. It was
written by Robert C. Bolles, Raphael A. Finkel, Richard L. Paul, and
Russell H. Taylor.
The English language has no neuter personal pronoun; without
any implication of sexism we use the feminine form in its place.
Work supported, in part, by the hand-eye table.
The views and conclusions contained in this document are
those of philosophical inquiry and should not be interpreted as
necessarily repesenting the official policies, either expressed or
implied, of any of the funding agencies.
INTRODUCTION
The development of mechanical manipulators during the Late
Middle Ages of 1948 soon led to the realization that most tasks
require position and force feedback. For the last ten years,
computers have been used as a controlling agent. This has led to
sophisticated servo programs which periodically compute an
incremental controlling signal from comparison of current manipulator
status against the planned status.
Elementary languages have been built for the purpose of
automating tasks more lengthy than simple motions. These languages
have much the flavor of assembly languages; primitive commands
involve those necessary for planning various kinds of motions, for
controlling the execution of the computed plans, and for simple
response to error conditions.
APT is one highly successful system for the automation of
parts-machining tasks. It provides open-loop control of metal
cutting machines and allows precision cutting along curved lines and
accurate workpiece positioning. The principal failings of APT
involve its poverty of descriptive ability for complicated motions,
the resulting limitation on the type of tasks which it can
accomplish, and its restriction to metal cutting machines.
Another example of a system for manipulator control is WAVE
at Stanford. It includes two Scheinman electrical arms and software
for preparing moderately complex plans. The most impressive
accomplishment of this system has been the assembly of a water pump,
which was done with one arm, and optionally made use of visual
feedback. Further achievements have included a primitive two-arm
task: the assembly of a hinge. WAVE currently can produce
independent plans for the two arms. The only form of coordination is
achieved by halting one arm and starting the other one. The model of
world knowledge contained in the system is quite limited: A small
number of hand positions can be remembered; each of these positions
can be associated with an "offset" between planned position and real
position. This information is obtained during the actual execution
of a plan,and allows run-time modification of trajectories. The
sophistication of the control structure is limited; there are only
simple jumps, including conditionals on error conditions. When a
plan fails due to excessive requests on hardware ability, the user
may request the continuation of the plan. WAVE also has a clumsy
interface with SAIL, which is a high-level algol-like language; thus,
in principal, it can take advantage of SAIL's algebraic power.
None of the currently available task-automation languages is
capable of efficiently sequencing tasks or planning other strategy
for the execution of a task; they only can translate explicit
instructions into machine-executable form. In this sense they can be
thought of as "assembly languages"; some of them are rather fancy,
with a macro facility, a few named variables, and some simple
arithmetic, but none can be called a high-level language.
The availability of new types of hardware (for example,
force-sensing wrists) and the increasing complexity of the tasks we
wish to perform, as well as the recognized failings of WAVE, have led
us to the design of a new hand language, which is called HAL. It is
a very high level language for the specification of manipulatory
tasks (especially assembly tasks) in a world of several arms and
other devices. The following pages contain a description of HAL.
GOALS
A full language for planning manipulatory tasks of the
complexity required for assembly needs many features, some of which
do not exist in any current system. We have identified these goals:
HIGH LEVEL LANGUAGE FEATURES
1) The language must be able to describe those things
important to the programmer. This implies that there should be
datatypes natural to the tasks at hand. Principally, there should be
a datatype whose value is a location-orientation in 3-space.
Secondarily, there should be vectors and scalars. Arithmetic
operations should be defined on these datatypes to make them useful.
2) We want to write entire programs in a natural manner. The
machine-language aspect of current manipulation languages makes it
cumbersome to write long programs in any structured way. What is
desired is a language which lends itself to a more systematic and
perspicuous programming style. Algol-like control structures would be
a vast improvement over assembly-like straight code with jumps.
3) Simultaneous execution of several processes should be
available. A general mechanism for simultaneity is desired.
FULL MOTION SPECIFICATIONS
1) Experience with WAVE has shown that calculating
trajectories is a desirable feature, although a time-consuming one.
Therefore, a motion should be calculated in a "compilation" step, and
executed at a later time, perhaps repeatedly. This leads to a clear
distinction between compile-time and runtime.
2) Since we are aiming for a system of use on the factory
floor, and since a large time-sharing machine is incapable of
supporting real-time control over many devices, execution of plans
should take place under the control of a small computer (like a
PDP-11), many of which could be distributed in the work area.
Trajectory planning, however, is not real-time constrained, and is
better done on a large computer (like a PDP-10).
3) Since locations are not known exactly during planning of a
trajectory, there should be a clear distinction between planned
values and runtime values. Planned values will be used for
trajectory calculation; at runtime, these trajectories will be
modified if necessary to account for any discrepancies.
4) The user should be able to demand that a trajectory pass
through certain intermediate points. The primary use of this is to
avoid collisions (especially with the table) during the motion. It
is also useful for specifying complicated motions, such as those
necessary to accomplish spray-painting.
5) It is necessary to test for a wide range of exceptional
conditions during arm motion and to take appropriate action as soon
as any of them occurs. These conditions could include excessive
force being exerted, excessive closeness of the arms, completion of
some related task being done independently by other devices, an
interrupt generated by the user, a certain time arriving, and a
temperature senser reaching a critical point. The appropriate
actions might be to start up a new concurrent process, to terminate
something already active, to notify the user, or to file away a
statistic in a table somewhere. It is also useful to change the
nature of the test during a motion, if different segments require
different types of monitoring. This concept can be generalised to
include the modification of a motion during its execution to
accomodate to changing conditions. In any case, it should be easy
for the user to specify exactly what is being tested, what the scope
of the test is (that is, when should it start and when should it
end), and what to do if it triggers.
THE RUNTIME SYSTEM
1) The runtime system (which, as previously mentioned, is
intended to reside in a minicomputer) must support simultaneous
executions of several processes. Three basic types of process have
been identified: An interpreter, which does arithmetic; a servo,
which controls one joint of one device; and a monitor which
continually examines conditions. These must be managed in some
(simple) scheme of time-sharing with guaranteed response for the
latter two types of process.
2) There must be enough information available at runtime for
the proper modification of trajectories immediately before they are
executed.
3) The system must be capable of using vision and other yet
unpredictable forms of feedback must Vision would be quite useful in
searching for objects and testing for adequacy of assembly. It is
conceivable that vision will be used for the servoing of an arm; this
implies that the feedback loop must be active during motions as well
as when the world is stationary. Other dynamic feedback (like
force-sensing wrists) could make the capabilities of the arms much
greater in dealing with non-rigid materials like cloth or rope. What
is needed is a way of specifying calls to these "external" devices so
that when they become available, they can be meshed into the system
without much difficulty.
4) There should be a way to investigate the contents of the
runtime system, both variables and code, in order to patch simple
mistakes discovered during the course of a production run. This
feature would be especially useful for debugging the compiler.
ADVANCED LANGUAGE FEATURES
1) Assembly tasks require that one object be affixed to
another. We wish to model this by having a semantic attachment
between objects. When one moves, the second one should move (that is,
its planning value should be modified) accordingly. This
"attachment" concept carries over to the runtime system, which does
the equivalent modifications of the actual values. This saves the
user untold bookkeeping operations to determine where an object is
after its base has been moved.
2) Attachment is not the only world information that should
be kept in the compiler. Other desirable information includes not
only all planning values but also information like the accuracy
within which the planning value is known, how heavy objects are, how
many faces an object has on which it can rest, how wide the fingers
of an arm should open to grasp it.
3) Ability to assist in the preparation of a program. This
is a wide-ranging issue, which involves at least these goals: To be
able to compile a piece of code and then to try it on the spot; to
delete or replace sections of previous code; to ask the arms for
status information during the coding process itself for the purpose
of setting constants and for implementation of a "learning by
showing" strategy. It should be easy for the user to recover from
errors discovered during any phase of debugging. The compiler itself
should make a great number of semantic checks, like assuring that a
proposed motion will not hit some object (although this is a
difficult problem which has not yet been satisfactorily solved), or
that simultaneous independent motions are not being requested for the
same device. Use of the graphics system should be made to depict the
world as the compiler sees it during compilation.
→→→→→RCB should rewrite 4:
4) There should be a program library. What is needed is to
be able to program frequently-needed procedures, like "PUT IN A
SCREW", in some generality, and then to be able to use them in the
future by supplying from the model whatever information was left out.
A solution is to have library routines capable of being conditionally
expanded, depending on the state of the planned world at the moment,
so many similar macros can be written together for tasks like "PUT IN
A SCREW AT CENTER OF TABLE", "PUT IN A VERY LONG SCREW", "PUT A
SCREW THROUGH A THIN BOARD", and others, differing not only in the
values of the expected parameters but fundamentally in the method
used to accomplish the task.
5) Ability on the part of the system to automate simple
decisions based on world information. An example would be for the
system to decide where best to locate an object for future work when
the programmer requests that the system pick the place for her.
→→→→→ RHT should rewrite 6:
6) Ability to say "BIND X TO Y" and expect that the knowledge
contained about x and y suffices to allow the compiler to generate
all the code needed for the attachment of the two objects, including
what the means of fastening is to be, where it will be done, and
exactly what sequence of operations is necessary to accomplish the
task. What we are asking for is a program capable of strategy
formation for the achievement of assembly tasks based on incomplete
knowledge, incorporating whatever fragmentary knowledge is available
about the world, techniques of assembly, what library routines are
available, what sort of global costs and success rates can be
expected for different approaches. This strategist (or sequencer,
perhaps) should be able to query the user concerning details which
are essential for the planning, and should be able to come up with
code recognizable as something the user might have typed in had he
been willing and able to go to the trouble.
A SAMPLE DIALOG WITH THE HAL SYSTEM
Here is a sample conversation a user might have with HAL. It
demonstrates the following features: Typing in source code by hand,
requesting source code to be read from a file, immediate execution
of commands by the arm, return of values from the arm, loading
compiled code into the runtime computer, and executing that code.
⊃COMPILE TTY | Request to read in
| from TTY for compilation.
↔MOVE YELLOW | Simple move statement
TO [(20 30 1):(π 0 0)]; |
ENDM; | An END matching MOVE.
|
FRAME PLACE1; | Declaration
PLACE1 ← YELLOW; | Assignment
FRAME PLACE2; | Declaration
PLACE2 ← PLACE1+(0 0 5); | Assignment
↑Z | End of file
⊂NO ERRORS. COMPILED: TTY(1)⊃ | Compiler message.
|
⊃IMMEDIATE | Request for an immediate action
↔MOVE YELLOW TO PARK; | User wants to park the arm
⊂DONE⊃ | And does
|
⊃EXECUTE | Request to execute compiled code
⊂LOADING TTY(1)⊃ | First, loading to be done
⊂EXECUTING TTY(1)⊃ | Message at start of execution
⊂DONE⊃ | Message at end of execution
|
⊃READ PLACE3←YELLOW | Request to read hand position
⊂PLACE3 DECLARED FRAME⊃ | Declaration defaulted
⊂PLACE3 = [(19.9, 30.1, 1.1):(3.1, 0, 0.1)]⊃ | Indication of what was set
|
⊃WHERE PLACE4 | Request for value of variable
⊂PLACE4 = (12.0, X, 55)⊃ | This frame has a parameter
|
⊃COMPILE HACK.HAL[1,LOU] | Request for compile from file
⊂ERROR IN LINE 310 OF HACK.HAL[1,LOU]. | Parser error message
THEN | Gives line with <lf>
CONE | at point of error
OPTION⊃? | User typed "?"
I: INSERT REPLACEMENT TEXT | A list of options to user
Z: USE LINE EDITOR TO FIX |
M: SHOW MORE CONTEXT | This would give entire statement
F: FLUSH TO END OF STATEMENT |
E: SWITCH TO E | E is a text editor
S: SWITCH TO SOS | SOS is a text editor
Q: QUIT. ABORT COMPILATION |
OPTION⊃I | User chooses to insert replacement
↔ THEN DONE | "CONE" changed to "DONE"
↑Z | End of file
⊂ERROR IN LINE 520 OF HACK.HAL[1,LOU]. | trajectory calculator error message
MOVE YELLOW | Only first line of statement given
THE DESIRED MOTION GOES OUT OF BOUNDS IN JOINT 3| A bad motion
IN THE FIRST SEGMENT OF MOTION. |
OPTION⊃E | User chooses to edit with E.
⊂SWITCHING TO E. TO RETURN, <CTR>XG<CR>⊃ | Universe is saved for reentry.
⊂YOU ARE BACK AT HAL. | Editing done
COMPILATION OF HACK.HAL[1,LOU] ABORTED⊃ | After an edit, compilation aborts.
|
⊃COMPILE HACK.HAL[1,LOU] | Request for recompilation
⊂NO ERRORS. COMPILED: TTY(1), HACK.HAL[1,LOU]⊃| Compilation succeeds.
|
⊃LOAD | Request to load into servo
⊂LOADED: TTY(1), HACK.HAL[1,LOU]⊃ |
|
⊃STATUS | User wants to know where she is
ARM AT [(19.9, 30.1, 1.1) : (3.1, 0, 0.1)] | Arm location
COMPILED: TTY(1), HACK.HAL[1,LOU] | Compilation status
LOADED : TTY(1), HACK.HAL[1,LOU] | Runtime status
|
⊃EXECUTE | Request for execution
⊂EXECUTING TTY(1), HACK.HAL[1,LOU]⊃ |
|
⊃STATUS | User wants to know where she is
ARM AT [(24.1, 30.1, 5.3) : (3.1, 0, 0)] MOVING | Arm status
SERVO AT LINE 320 IN HACK.HAL[1,LOU] | Servo status
⊂INTERRUPTED BY RED BUTTON⊃ | Runtime error message. User
| interrupted motion.
SERVO AT LINE 180 OF HACK.HAL[1,LOU] | Servo status
|
⊃PROCEED | Request to continue motion
⊂JOINT 4 HAS EXCESSIVE FORCE. | Runtime error message.
SERVO AT LINE 150 OF HACK.HAL[1,LOU] | Servo status
|
⊃DELETE 1 | Request to delete last compilation
⊂DELETING HACK.HAL FROM SERVO | Removed from runtime
⊂DELETING HACK.HAL FROM COMPILATION | Removed from world of compiler
|
⊃E | Switch to E.
⊂SWITCHING TO E. TO RETURN, <CTR>XG<CR>⊃ |
⊂YOU ARE BACK AT HAL⊃ |
|
⊃COMPILE HACK.HAL[1,LOU] | Request for compilation
⊂NO ERRORS. COMPILED: TTY(1), HACK.HAL[1,LOU]⊃| Compilation succeeds
|
⊃SAVE WORLD IN W1 | User wants world saved in named
⊂WORLD SAVED IN W1.WLD⊃ | location; this is done.
|
⊃RESTORE WORLD FROM W0 | Request to restore previous world
⊂W0 NOT FOUND⊃ | Expander error message
|
⊃RESTORE WORLD FROM W00 | Request to restore previous world
⊂DONE |
NOTE: TTY(1), HACK.HAL[1,LOOU] STILL COMPILED.⊃| This is done, but previous stuff
| is still around.
⊃BYE | Request to leave the room.
⊂FINAL STATUS: | A final status rundown
LOAD MODULES READY: TTY(1).HLD, MACS.HLD |
ARM AT [(19.9, 30.1, 1.1) : (3.1, 0, 0.1)] |
GOODBYE.⊃ |
EXIT
.
GENERAL OUTLINE OF THE HAL SYSTEM
The HAL system consists of six principal programs capable of
communication with each other. The sytem resides on two computers:
The PDP-10 for all planning, and the PDP-11 for the execution of the
plans. Of the six programs, only the runtime system is in the PDP-11.
1) The SUPERVISOR is the top level of the system. It
provides an interface between the user and the other parts of the
system. Specifically, it listens to the console and interprets
input as requests to the other system routines. It listens to the
PDP11, and reports to the console during error conditions. It
listens to the parser, the expander, and the trajectory calculator,
and transmits messages between them and to the user. In the sample
dialog given earlier, the supervisor identifies its prompts by "⊃".
2) The PARSER is capable of reading source code from either
the console or a file. Its purpose is to form parse trees and do
some simple manipulations, such as assigning line numbers, causing
listings to be directed to the appropriate file (if desired),
expanding text macros, and keeping a primitive symbol table. If a
syntax error is discovered, it informs the supervisor, which will
give the user several options, including aborting the compilation,
making local modifications on the spot, or switching temporarily to
a text editor. In many cases, control will be returned to the
parser, and it will continue to create parse trees from the input.
Periodically (after every statement is parsed), it calls on the
expander to manipulate the nascent parse trees.
3) The EXPANDER takes the parse trees produced by the parser
and serves three basic functions: a) (expanding) keeping a world
model for each point of the program, including information on the
planned values for all variables, the attachments that have been
made, and the assertions which the user has made about the nature of
the objects with which she is dealing. This world model is used to
expand those conditionals which depend on the state of the world.
(These are called world conditionals.) The library of utility
routines previously programmed is available to the expander, and it
resolves calls on those routines. b) (binding) The second task of
the expander is to pick values for those variables which the user has
left unbound and has explicitly requested be chosen within given
constraints. The expander attempts to make a good decison as to the
best way to bind these variables. If it is not possible to make this
binding without further information, the expander can query the user
for more information. The world model is used extensively during
this process of specification. c) (sequencing) The third and hardest
task of the expander is to make global strategy decisions in the case
that the user has not specified even the order in which the assembly
is to progress. The expander must sequence the operations into an
order which facilitates the assembly. The decisions made on this
global level interact strongly with those made on the local level
mentioned above; that is one of the reasons that expanding is a
difficult task. The expander can explain any of its decisions to the
user.
The output of the expander is a tree very much like that
which it took as input, except that no choices are left; all values
are explicitly specified. This structure is then passed on to the
trajectory calculator.
4) The TRAJECTORY CALCULATOR takes the expanded code and
computes the requested trajectories for the manipulators. Tables of
interpretable code are generated, including arithmetic and
assignment operations. monitoring of conditions, and graph-structure
building operations (the runtime system keeps track of physical
attachment of objects). For motions, detailed instructions are
emitted specifying how each joint of each arm is to behave, what
conditions are to be monitored, what to do if one of these conditions
triggers, and what computations to make at run-time for the
modification of these trajectories.
Also, the trajectory calculator should be able to provide
information to the expander. For instance, it should be able to
predict the runtime effects of a given modification of a planned
trajectory. This information is useful to the expander in deciding
how many "different" trajectories must be planned for a given motion
request.
There are several errors which the trajectory calculator can
detect. A request might take the arm outside its range, or force a
joint to exceed its velocity limits. It may discover that there is a
possiblity of collision between the two arms, or between the arm and
some object on the table. In order to carry out these tests, it may
request the user to assure it that some object lies within a certain
region, or it may give the user a warning. The world model is used
for much of this calculation. At its discretion, the trajectory
calculator may make some critical motions very slow, so that an
impending collision will be seen before it happens.
The output of the trajectory calculator is stored in binary
files, for loading into the PDP11.
5) The LOADER takes the load modules prepared by the
trajectory calculator and enters them into the PDP11 runtime system.
A small amount of linking is made at this time to resolve references
which were left dangling in the previous programs loaded into the
PDP11. (It is understood that a run-time error will result from any
access to an entity which has not been loaded.) This loading is
carried out in an incremental fashion; new modules are put in after
old ones. Since the memory size of the PDP11 is not infinite, the
process of loading may be only to prepare the disk space accessible
from the PDP11 so it can get at its code.
6) The RUNTIME SYSTEM is the set of programs which reside in
the PDP11. This system includes a simple monitor for time-slice cpu
sharing and process control, and a set of dynamically created
processes. These are of three basic types: a) An INTERPRETER
examines the tables prepared by the trajectory calculator and
executes the numeric computations requested. When a move is to be
started, the interpreter sprouts a servo for each joint and waits
until all these servos terminate. b) A SERVO handles the motion of
one joint. It coordinates that joint to the system clock, following
the trajectory that was planned by the trajectory calculator and
modified by the interpreter just before the servo was sprouted. (This
modification serves to adjust for the discrepancy between the planned
locations of objects and the runtime locations). c) A
CONDITION-MONITOR is sprouted to monitor error conditions (or
anything else that the programmer has specified). If it should
discover that its condition is satisfied, it sprouts an interpreter
to take appropriate action. Together, the interpreters, servos,
and condition-monitors constitute the bulk of the runtime
environment. The latter two determine how long they are willing to
wait before again regaining the cpu, and then they make reservations
for time slices. The system serves to awaken the correct process at
the beginning of each millisecond time slice.
The runtime system can also communicate with the supervisor,
either to request information, to report status, or to indicate
failure. The runtime system is started up in the first place by the
supervisor, which instructs it where to begin execution.
OVERVIEW OF THE HAL SOURCE LANGUAGE
HAL is a very high level language for the specification of
manipulatory acts. A discussion of HAL must include the following
four areas: control structures, data structures, motion
specifications, and world model specification. We will treat these
topics in that order.
CONTROL STRUCTURES
TRADITIONAL ALGOL STRUCTURES
HAL has many of the traditional ALGOL control structures,
including the statement, the block, the IF-THEN-ELSE conditional,
the WHILE loop, the FOR loop, and the GOTO (which in HAL is written
JUMP. JUMPs will not be implemented at first, because they confuse
the flow analysis needed for maintaining planning values, and because
it is possible to accomplish much without them). The simple
statement can be of several varieties: Assignment, declaration,
manipulation, world modification, condition monitoring. The
assignment statement is of the general form
FROB ← A + (2, 0, 0),
that is, a variable name, a left arrow, and a suitable expression.
The types of expressions available will be discussed under the rubric
of data types. Declarations are allowed anywhere in the code that
other statements are allowed; this facilitates typing in a program
from a terminal. Manipulation, the fundamental purpose of HAL, will
be discussed fully in the section on motion specifications. World
modification actually takes place after every assignment and motion,
but some statements are purely for the purpose of changing the
compiler's notion of the world. All world model specification will
be discussed later. Condition moditoring is discussed below.
COBEGIN-COEND
In addition to these traditional structures, there are also
some special ones for specifying simultaneous independent action. The
principal device for this is the COBEGIN-COEND pair, which brackets
statements whose execution is meant to begin simultaneouly. The
termination of the block occurs only when each of the statements in
the scope of the COBEGIN has terminated. To achieve simultaneous
coordinated motion, one uses a special form of the move commands
which will be discussed later.
THE CHECK STATEMENT
Since library routines will be commonly used, it is necessary
to have some way of checking that necessary preconditions are met as
the first steps of the library routine. The way this is done is with
the CHECK statement. A simple example is this: CHECK X=3 ∧ Y>5. The
contents of the check may be any boolean expression, including checks
on the current world model.
ON MONITORS
It is often desired to monitor some set of conditions
throughout a block of code. A special kind of statement which allows
the user to do this is the ON statement. A simple example is "ON T >
5 DO STOP YELLOW", which while active will monitor the magnitude of T
and if it should become greater than 5 will cause the yellow arm to
stop, if it is moving. An ON monitor has two states: enabled and
disabled. Generally, an ON monitor will be enabled as soon as its
defining statement is executed, and it becomes disabled when its
block is exited. Also, as soon as an ON monitor triggers, it becomes
disabled until explicitly reenabled. Reenabling is done by executing
the statement ENABLE within the conclusion (that is, the statement
following the DO). It is possible to name ON monitors; a monitor
named "CH" will be enabled when a statement of the form ENABLE "CH"
is executed, and is disabled either under the conditions named above
or when it is explicitly turned off by a DISABLE statement. If it is
desired to have an ON monitor initially disabled, preface the ON with
the word DEFER.
The condition which is being tested must be a simple numeric
inequality or equality, possibly using some continually evaluated
function. Boolean combinations are not allowed.
Some examples of ON monitors:
"FUDGE" ON TEMPERATURE > 400 DO OUTPUT("BURNING");
DEFER "WAIT" ON RES = 1 DO DISABLE "FUDGE";
ON MARK > 3 DO ENABLE "WAIT";
It should be noted that this ability to enable and disable
monitors explicitly is a non-structured concept; using it will often
lead to unintelligible programs. In any case, scope rules must be
observed; it is not legal to enable or disable a monitor in a
parallel or subsidiary block. This means that two statements,
simultaneously executing inside a COBEGIN block, are not allowed to
interfere with each other's ON monitors. It is generally wise not to
use named ON monitors unless their particular power is needed.
The clause after DO in the ON statement (that is, the
conclusion) may be any statement except a jump, so one can get
complex examples like this:
ON DURATION > 5 DO
BEGIN
"BIND" ON FORCE(Z)>10 DO STOP YELLOW;
ON DIST > 3 DO
BEGIN
DISABLE BIND;
VEL ← 40;
END;
END;
The existence of ON monitors raises the question: "when is a
block considered to be finished?" It can happen that all the
executable statements have finished, but some ON monitors remain.
This situation is often sterile; nothing can happen unless one of the
conditions happens to trigger, which may or may not happen.
Therefore, a block is declared finished when no interpreters remain
active within it. This means that if even one ON monitor has caused
an interpreter to start executing (to perform the statements in the
conclusion), then the block is not exited until that interpreter is
done. But a block may be exited while some ON monitors are still
enabled; this automatically disables them.
The user must be wary of the relative speeds at which her
various pieces of code in ON test conclusions get executed. When an
ON test triggers, any initial statements of enabling or disabling are
done immediately, but any arithmetic is scheduled to be done at some
point in the near future. Therefore it is not possible to guarantee
that a critical computation happen immediately. If the user desires,
she may use the word CRITICAL at the start of the conclusion, and
UNCRITICAL at the start of that code which need not be guaranteed
immediate execution. HAL automatically assumes CRITICAL before
statements of enabling and disabling, and UNCRITICAL immediately
following. Caution: if critical computations take too long
(currently about 1 millisecond), there will be a severe runtime
error.
The UNITS statement
Numbers are quite often used for measurements, and many
different systems of measurement exist. The UNITS statement serves
to inform the compiler which units are being used. It uses its own
system for internal consistency, and does any scaling when necessary.
The default units, which the compiler itself uses, are listed first
in the following lists:
Time: milliseconds, seconds, jiffies (that is, thirds: 60ths
of a second), minutes.
(The grain of the runtime is on the order of jiffies).
Distance: centimeters, inches.
Mass: grams, ounces, pounds, kilograms.
Angles: radians, degrees.
Rotations: Euler, Bolles, Taylor, Geomed. (These are explained
in the discussion on dataypes.)
An example:
UNITS SECONDS, DEGREES, TAYLOR;
COMMENTS
As in Algol, comments are prefaced with the word COMMENT and
terminated by a semicolon.
LABELS
A LABEL is a point in the program to which a jump may be
made. Labels also mark some ON-monitors. Labels are not declared. An
example:
FOO: A ← A + 1;
IF A < 100 THEN JUMP FOO;
Labels are in general useful mainly for debugging, and not for
program control, especially since JUMP will not be implemented at
first.
DATA STRUCTURES
DECLARATIONS. PLANNING VALUES. ASSERTIONS.
There are several available types of variables and constants,
as described below in detail. Each variable must be declared
somewhere before it is used; however, it is not necessary that this
declaration be at the top of a block. If a variable which has not
been declared is encountered, an attempt will be made to guess at its
type. (The compiler will, of course, give a warning.) This can lead
to unfortunate results, so it is best to declare all variables. The
compiler keeps track of a "planning value" for each variable. At
first, this value is "undefined"; any expression using an undefined
value itself has undefined value. Planning values become defined
through two mechanisms: Assertions and assignments. The statment
ASSERT X=3 has the compile-time effect of setting the planning value
of X to 3. The statement X←3 has the effect of setting the planning
value to 3 and causing code to be generated for the runtime to set
the value of X to three at this point in the program. If a variable
is changed within a loop, its planning value will be undefined except
between assertions about it and the point in the loop where its value
is changed. The use of JUMPs so complicates the bookkeeping for
planning values that they are highly discouraged. The purpose of
having planning values is severalfold, the most important use being
the calculation of proper trajectories. An example is ASSERT YELLOW
= YPARK, which tells where the yellow arm is. Since at planning time
it is expected that some values will be known only roughly, provision
is made for the runtime to modify all trajectories before executing
them. This is the subject of a later discussion. The planning value
of any variable is accessible to the programmer: #A is the planning
value of the expression A.
ALGEBRAIC DATATYPES
The simplest datatype is the SCALAR, which is internally
represented as a fixed-point number. Scalars are used as time
intervals, space intervals, and as substructures upon which the more
complicated datatypes are built. There is a UNITS statement which
allows the user to set the measurement system she would like to use,
so that a time scalar will be unambiguously interpreted as meaning
seconds, or jiffies, or whatever she wants. Some examples:
SCALAR A, B;
A ← 2.4;
UNITS CENTIMETERS, SECONDS,RADIANS;
B ← 3*A;
The next datatype is the VECTOR. A vector is written as a
triple of scalars separated by commas or blanks. An example is "(2 X
4.3)". Vectors can refer either to location offsets (that is,
translations) or to orientation offsets (that is, rotations). The
context is sufficient to determine which of these meanings is
intended. When a vector refers to a translation, it is understood to
be in TABLE coordinates. When a vector refers to a rotation, it can
either be represented in Euler angles (rotations about z, x', z''),
Bolles angles (rotations about x, y, z), Taylor angles (rotations
about z, x', y'), or Geomed angles (a, b, c, specifying the vector of
rotation whose magnitude is the angle of rotation). The UNITS
statement serves to set a default mode (as well as to determine
whether degrees or radians are being used).
Examples:
VECTOR V1, V2;
V1 ← (3 1 A);
V2 ← V1 ∂ (π 0 0);
A FRAME is a location with an orientation. It has two basic
interpretations, which are closely related: 1) a hand position, and
2) the location and orientation of any object. TABLE is a predefined
frame. (It holds table coordinates). Each arm (currently, YELLOW and
BLUE) is also a predefined frame; these frames are "read only" in the
sense that they may not appear to the left of an assignment arrow.
The values of YELLOW and BLUE are implicitly modified by arm motions,
however. The rest positions of the two arms are YPARK and BPARK,
which are also read-only.
Frames are described by a pair of vectors: one for position
and one for orientation. An example of a frame expression is [LOC :
ORIENT] where LOC is a vector specifying location, and ORIENT is a
vector for the orientation (with respect to the table). It is
possible to ATTACH one frame to another; this has to do with world
models, and will be discussed more fully later. The basic idea is
that whenever the value of the parent frame changes, all the frames
fixed to it are assumed to have moved with it. Examples:
FRAME F1, F2;
F1 ← [V1 : V2];
F2 ← F1 ∂ -V2;
A PLANE is constructed from two vectors: the plane passes
through the first vector, and the outward-facing normal is in the
direction of the second vector. The syntax is VECTOR1 \ VECTOR2.
Thus, the surface of the table is (0 0 0)\ Z.
Planes divide the universe into three sets with respect to
the plane: inside, on, and outside. Outside are all points which
are on the side of the plane towards the outward-facing normal. To
determine where a point lies with respect to a plane, that is,
whether it is inside, on, or outside the plane, use the expression
VECTOR . PLANE. It is a scalar whose absolute value is the shortest
distance from the vector to the plane, and whose sign is negative if
the vector is inside the plane, 0 if the vector is on the plane, and
positive if the vector is outside the plane.
It is occasionally useful to construct a plane from four
scalars: the first three are the outward pointing normal vector
(which will be normalised if necessary); the fourth is the opposite
of the distance to the origin (of table coordinates). The way to
express such a plane is like this: [S1 S2 S3 S4].
Examples:
PLANE P1, P2;
P1 ← LOC(F1) \ (F1*X); COMMENT: Y-Z plane of F1;
P2 ← P1 + (P1.(0 0 0))*NORMAL(P1); COMMENT: Moves P1 to origin;
S1 ← V1 . P1;
P1 ← [2 4 3.2 8.1]; COMMENT: Fairly meaningless;
A TRANS is an operator acting on vectors, frames, planes, and
other transes. It is defined as the relation between two frames. An
example is FRAME1 → FRAME2. The value of this trans applied to
FRAME1 is FRAME2. That is, (FRAME1→FRAME2)*FRAME1 is identically
equal to FRAME2. A trans can be built up from a rotation and a
translation; the expression is [TRANSLATION | ROTATION]. Note that
rotation is applied first. Some people find it helpful to think of
frames as transformations: The transformation associated with a frame
A is "TABLE → A". When a frame is used in a context demanding a
transformation, it will be understood as a shorthand for the trans
leading from the table. Transes operate on the left. Examples:
TRANS T1, T2;
T1 ← F1→F2;
V1 ← T1*V2;
T2← T1*T1;
ARITHMETIC
Here is a summary of the arithmetic expressions available.
They are grouped by the type of their values. These abbreviations
are used: `s' = scalar , `v' = vector , `f' = frame, `p' = plane, `t'
= trans.
scalar expressions:
s + s scalar addition (commutative)
s - s scalar subtraction
s * s scalar multiplication (commutative)
s / s scalar division
v . v dot product of two vectors (commutative)
| v | magnitude of vector
p . v signed distance from vector to plane
vector expressions:
(s s s) forming a vector from three scalars
s * v dilation of a vector
v + v vector addition (translation of the first vector by
the second) (commutative)
v ∂ v rotation of the first vector by the second
t * v transformation of a vector
f / f difference (rotation) between two frames
plane expressons:
frame expressions:
[v : v] forming a frame from location (first vector) and
an orientation (second vector)
f + v translating a frame; modifies only the location part
f ∂ v rotating a frame; modifies only the orientation part
t * f transformation of a frame
plane expressions:
v \ v formation of a plane. Goes through first vector, outward
pointing normal is in direction of the second vector.
[s s s s] formation of a plane. First 3 scalars form outward-pointing
normal; last scalar is opposite of distance to (table)
origin.
p + v translation of a plane by a vector
p ∂ v rotation of plane (about table origin) by a vector
t * p transformation of a plane by a trans
trans expressions:
f → f transformation which leads from the first frame to
the second
[v | v] composing a translation, then a rotation to make a trans
Even though the translation is written first,
it is applied after the rotation.
t + v translating a trans; modifies only the translation part.
t ∂ v rotating a trans; modifies only the rotation part.
t * t composing two transes. Transes operate on the left.
PREDEFINED CONSTANTS AND VARIABLES:
π is 3.14159...
TABLE is a frame which has standard table coordinates.
BLUE is the location of the blue hand.
YELLOW is the location of the yellow hand.
BPARK is where the blue hand parks.
YPARK is where the yellow hand parks.
X is (1 0 0).
Y is (0 1 0).
Z is (0 0 1).
Any expression preceeded with the symbol "#" means "the planning value
of this expression", that is, a constant is substituted for the entire
expression in the expander.
EXTRACTION FUNCTIONS:
LOC(FRAME) is a vector whose value is the location of the frame.
ORIENT(FRAME) is a vector whose value is the orientation of the frame.
XSCAL(VECTOR) is the X coordinate of the vector.
YSCAL(VECTOR) is the Y coordinate of the vector.
ZSCAL(VECTOR) is the Z coordinate of the vector.
NORMAL(PLANE) is the outward facing normal vector of a plane.
SOME EXAMPLES OF ARITHMETIC EXPRESSIONS
In the following examples, assume these declarations:
FRAME F1, F2, etc;
VECTOR V1, V2, etc;
SCALAR S1, S2, etc;
PLANE P1, P2, etc;
A unit Y vector in F1:
F1*(0 1 0)
F1 * Y
F1's Z vector as seen from F2:
(F2→F1) * (0 0 1)
(F2→F1) * Z
V1 rotated 90 degrees about the table's Z axis:
UNITS EULER;
V1 ∂ (90 0 0)
F1's Y-Z plane:
LOC(F1) \ (F1*X)
A plane 3 units above the table:
(0 0 3) \ Z
(3*Z) \ Z
MOTION SPECIFICATIONS
COMPILE-TIME AND RUNTIME CONSIDERATIONS
All motion statements cause the compiler to make some plans
for the eventual execution of the motion. These plans are more or
less complicated, depending on the exact type of motion requested.
Those motions which depend on the value of some frames as parameters
to the action will be planned using the compile-time planning values
for all relevant frames.
Immediately before the arm starts moving on a trajectory, the
plan is modified to bring it into line with current values of frames.
The result of this last-minute modification is that if there is any
discrepancy between the runtime and compile-time understanding of
where any frame is, the servo will place the arm in the right place
nonetheless. There are limits to the proper use of this feature; if
the planning value is seriously in error (and this can mean anywhere
from a few inches to a foot, depending on the arm being used and its
configuration), then the attempt to make last-minute corrections will
either overstrain the arm or impair force and free sensing (discussed
below). It is the user's responsibility to foresee such
discrepancies in the planning value and to branch her program so that
several moves are planned (with ASSERT statements to inform the
compiler of the assumptions being used). The IF-THEN-ELSE statement
will be useful in performing the correct branch at runtime. Its
condition will most likely involve the location of a frame.
The last step of any motion is the reevaluation of the
location of the hand, and the updating, if necessary, of the values
of all frames attached to it.
SIMPLE MOVES
A move is simple if it involves only one arm. There are two
varieties of move: MOVE and GO. The former causes a smooth
trajectory to be compiled. Such a trajectory is the result of
splining together polynomial segments (usually third degree,
occasionally fourth) for each arm joint seperately. This trajectory
calculation is somewhat time-consuming, and is done completely at
compile time. The GO form lets the servo do all the calculation, and
all that the compiler generates is a list of points that the arm
should go through (basically, just the start and the stop points). In
this mode, the arm will stop after each segment of the motion. In
either case, the arm is expected to travel from its current position
to the final position, passing through any specified intermediate
positions. The standard way to avoid the table is to begin motion
directly away from it and to end motion directly toward it. There is
a default offset associated with each frame, called its "deproach",
which is used to calculate the first and the last of the
intermediate, or "via" points. The deproach of a frame is stored as
part of the world information.
An example:
MOVE YELLOW | Smooth motion, for yellow arm
TO FROBGRASP; | Name of (frame) destination
VIA SWING1, SWING2; | Two via-points
ENDM; | This END matches MOVE.
The first implicit via point will be the deproach point for whatever
frame at which the yellow arm is currently positioned. The last
implicit via-point will be the deproach point for frobgrasp.
At each of the via-points, several conditions may be
specified. These are velocity and upper or lower bounds on the time
required to reach this frame from the previous one on the list. Also,
one may specify that a piece of code is to be initiated when a VIA
point is achieved; this is done with a THEN construct. The statement
following THEN may not be a jump or a motion statement for the same
arm.
An example:
VIA F1 (VEL=3*Z), F2 THEN ENABLE CH1, F3 (VEL=0,
DURATION=5).
This specifies three via points. At the first, the velocity is to be
3*Z, at the second a scalar variable is to be set, and at the third
the velocity is to be 0 and it should take 5 seconds to get there
from F2.
Certain things must be specified for any move. First is the
arm which is to be moved. It can be named directly (as YELLOW or
BLUE) or by naming a frame which is to be moved: If FROB is attached
to a hand, it is perfectly reasonable to request that the frob be
moved to a particular location. So if FROB is a frame attached to
BLUE, then both FROB and BLUE are "controllable frames"; MOVE FROB is
perfectly legal. A discussion of frame attachment can be found in the
world model specifications.
Next, the destination frame must be specified. TO F1 means
that at the end of the motion, the controllable frame (assume it is
an arm) should coincide with the frame F1. MOVE FROB TO F2 means
that at the end of the motion, FROB coincides with F2. A notational
convenience about destinations: They can be specified in terms of
where the controllable frame is at the start of the motion. The
symbol for this is ⊗. That is, ⊗ is a frame which is the location
and orientation of the controllable frame at the start of the motion.
Thus, ⊗ + (0 0 1) is a frame 1 unit above the starting place (in
table coordinates).
OPTIONS FOR MOVES
ON requests that certain conditions be continually monitored
during motion. These can be conditions of any sort, including flag
checking, force checking, and time checking. If any monitored
condition triggers, the DO part associated with it will be executed.
This is exactly like the ON monitor outside a motion, except that the
conclusion may not include any motion statements. The "block" of a
motion-based ON monitor is the motion statement itself; exiting the
motion will disable the test.
Several functions can be tested continually; these include
force along a vector (FORCE(V)), time since beginning (DURATION), and
the force between the fingers (SQUEEZE).
One more "function" is testable: SUCCESS. This becomes true
when the motion terminates due to either having reached its
destination, or some ON-monitor having executed the statement
"SUCCEED" in its conclusion. (SUCCEED also stops the arm, of
course.)
An example:
ON FORCE(Z)>10 DO
BEGIN OUTPUT("OUCH"); STOP END.
TRACING is another option. It allows the user greater
control over the exact trajectory chosen for the move. The path can
be traced at whatever speed desired. The path, or "parameterized
frame", is a specification of what frame the arm is to go through
for each value of the parameter. Of course, one also specifies the
relation between the parameter and real time. It is also possible to
state the grain of the motion and the tolerance that is acceptable
(as a distance in 3-space).
An example:
MOVE YELLOW
TRACING CENTER + (COS(P),SIN(P),0);
FOR P ← 0 BY.1 UNTIL 2*π;
ENDM;
should move the yellow arm in a circle around CENTER.
Next comes the option of MAINTAINING ORIENTATION. This
causes the trajectory computed by HAL to try to maintain the same
hand orientation throughout the motion. Of course, the final
orientation must be the same as the initial orientation for this to
work at all.
USING lists a set of modes under which the motion is to be
performed. These can include duration control, force applied in
some direction, which directions should be free from position
feedback, and what the departure and approach should be (if it is
desired to override the defaults, which are properties of the frames
involved at the beginning and end of motion).
Duration refers to the time elapsed since the start of
motion. In an ON-monitor, one can check for duration becoming too
long. In the USING construct, duration is merely a note for how long
the trajectory should be planned to take. One can use ≥,=,or ≤ for
this, although ≤ is most likely risky.
Force specifies both a direction and an intensity. During
the motion, an attempt will be made to apply the required force.
This is done by applying certain forces in some combination of arm
joints. Which arm joints are affected is decided by the compiler; if
the motion is long, it is likely that the particular joints applying
force will be scheduled to change during the motion, as the aspect of
the arm changes. To get a force in the hand's Z direction, say, one
would write FORCE = @ * Z, where @ is a symbol meaning "the location
of the controllable frame, as continuously changing during motion."
A free direction is one in which all position errors are
ignored by the servo. As for forces, the compiler translates this
into a set of joints which are to have the position feedback
disabled, and this set may vary throughout the motion. Once again,
the @ may be used to refer to the controllable frame as it moves.
It is possible to free more than one direction, or apply
force in more than one direction. In this case, the directions
specified for force must be orthogonal, as must the directions
specified for free. This restriction is enforced by the requirement
that multiple forces and frees all be set with respect to the
cardinal directions of one frame. Examples:
USING FORCE = FROB*Z, FORCE=FROB*X, FREE=HAND*Y, FREE=HAND*Z;
USING FORCE = (2 1 0), APPROACH = FROB * Z;
USING FREE = X, FREE = Y, DEPARTURE = NULL;
Since both force and free are translated by the compiler into
special handling of certain joints, surprises can result from large
discrepancies between the planning values and the actual runtime
values. The motions will go through the right places, but the
directions of force and freedom may be wildly wrong.
The notions of force and free are hardware-dependent; they
depend on the particular arm in use. Hopefully, as more
sophisticated arms become available, USING can be extended to handle
whatever new capabilities exist.
COMPLEX MOVES
A complex move is one which involves more than one arm at a
time. A distinction can be made between moves which merely require
simultaneous acquisition of "agreement points" (let us call this weak
synchrony), and those which require true coordinated motion
throughout (strong synchrony).
WEAK SYNCHRONY
Weak synchrony is achived by pairing frames to make composite
VIA points and destinations. A paired frame has the form: {F1, F2}.
Here is an example of a move statement using paired frames:
MOVE {YELLOW, BLUE}
VIA {Y1,B1},{Y2,*},{Y3,B2};
TO {Y4,B3};
ON {FORCE(Z)>3,*} DO STOP;
ENDM;
The via list is composed of a set of paired frames, where *
indicates "don't care". In the example shown, the arms start
together, achieve Y1 and B1 simultaneously, the yellow arm passes
through Y2, and together they pass through Y3 and B2.
It is now more cumbersome to specify ON monitors, or
conditions in general. The paired construct applies for all the
optional fields; thus, one can write
USING FORCE={3*Z,(2*Y)*@} to get the yellow arm applying a
force of strength 3Z, and the blue one to have a force of strength 2Y
in the coordinate system of the blue hand.
The meaning of ⊗ and @ is now relative to which side of the
pair they occupy; in the example above, the left side always refers
to the yellow arm, and the right side to the blue. To override this
convention, one may use expressions like "@.YELLOW", or "⊗.BLUE".
The meaning of STOP in the example above is extended to both
arms at once; in order to specify only one, it is necessary to say
"STOP YELLOW" or "STOP BLUE".
STRONG SYNCHRONY
Strong synchrony involves one concept not included above: The
ability to specify the location of one arm throughout the motion in
terms of the location of the other arm. The construct which allows
this specification is COORIDINATING; it allows one to give an
expression for the location of one of the two arms. Suppose we wish
to keep both arms in "lockstep", that is, the blue arm should retain
its relative position to the yellow arm throughout the motion. (This
might be necessary for lifting some object by its two ends.) One way
to code this task is as follows:
MOVE {YELLOW, BLUE}
TO {Y1, *};
VIA {YA,BA},{YB,BB};
COORDINATING LOC.BLUE = LOC.YELLOW + ⊗.BLUE - ⊗.YELLOW;
USING FREE = {*, @.YELLOW - @.BLUE};
{MAINTAINING ORIENT, MAINTAINING ORIENT};
ENDM;
SEARCHES
A SEARCH is very much like a move. It is a means of
specifying repeated action in a spiral. As with a MOVE, it is
necessary to name a controllable frame which is to be moved. The ON
construct is exactly as for MOVEs.
One must stipulate what the plane of the search is to be.
This is accomplished in either of two ways: ACROSS <plane> means the
search is to take place in the plane specified. If the controllable
frame (say the hand) is in fact not in that plane at the start, then
the plane parallel to the given one through the hand will be used. It
is assumed that the hand begins at the center of the search. The
other alternative is to say NORMAL_TO <vector>. This will specify
the plane you want for the search.
The size of the increment is specified in a USING construct.
An example is USING INCREMENT = 3.
The servo does almost all the calculating for searches; it is
fed the normal direction and the increment size.
Most important for the search is the REPEATING construct. It
is by this that one specifies what motion is to be performed at each
iteration of the search. It is advisable that the motion cause the
arm to return to the point at which it began, in order to assume the
same plane at the onset of each iteration. If this is not done, then
the servo will move it back each time anyway. When the search
succeeds (and it is the duty of the user to specify what success
means for each search) the search can be terminated in either of two
ways: by setting a flag in the REPEATING and checking it with an ON,
or by using the construct DONE inside the REPEATING at the right
place.
Here is a complete example:
SEARCH YELLOW
ACROSS P1;
REPEATING
BEGIN
FRAME SET;
SET ← YELLOW;
MOVE YELLOW TO ⊗-Z;
ON FORCE(Z) > 3 DO
BEGIN
FLG ← 1;
DONE;
END;
GO YELLOW TO SET ENDM;
END;
ON FLG=1 DO STOP;
ENDM;
CENTER
It happens at times that the hand is positioned around an
object, and it is desired to center the hand about it, closing the
fingers at the same time. The arm is meant to move over to accomodate
the object, should it be slightly off-center with respect to the
hand.
All this is accomplished by means of the CENTER command. As
with the SEARCH command, it takes as an argument the plane in which
the centering is to take place, either by the construct ACROSS
<plane> or by NORMAL_TO <vector>. The use of ON is just as in a
search or any other motion.
Here is a simple example:
CENTER BLUE
NORMAL_TO Z;
ON SQUEEZE > 4 DO STOP;
ENDM;
DEVICE CONTROL
STOPPING
Generally, an arm will stop its motion when it has achieved
its destination. Often it is necessary to stop it prematurely, for
example, if some error condition is detected. The statement STOP
YELLOW causes the yellow arm to be unconditionally stopped, and any
motion statement operating it will terminate. Each device has a name,
and can be stopped by name. Currently, the legal device names are
YELLOW, BLUE, VICE, DRIVER (an electric screwdriver), YFINGERS,
BFINGERS (The fingers of the two arms). STOP without any device name
is only legal within a motion command; it stops whatever device that
command is operating.
OPERATING OTHER DEVICES
There is a general command for operating devices other than
arms; it is hoped that this will be flexible enough for any device we
are likely to use (if not, we will add special new forms). Assume we
have the device TURNTABLE, which is capable of moving at any velocity
and for any length of time, but which cannot go to a particular set
point. Then the syntax would be this:
OPERATE TURNTABLE
WITH VELOCITY=3;
WITH DURATION=8;
ENDM;
The idea is that the WITH construct will suffice to account for any
special data (in this case, velocity and duration) peculiar to the
particular device. The OPERATE statement also allows the ON
construct, so it can test for special conditions and take appropriate
actions.
SCREWDRIVER CONTROL
The screwdriver is a hand-held device which can be run at a
range of speeds, in either direction. By convention, a positive
velocity means clockwise, and a negative velocity means
anticlockwise. The relevant reserved word is VELOCITY, which is
equated with the name of a scalar variable, which will be queried
each time the screwdriver servo wakes up to determine how much
voltage to supply the moter. This allows the velocity to change
during the operation of the device, perhaps under the control of a
parallel process which is monitoring some conditions.
An example:
OPERATE DRIVER
WITH VELOCITY=SP;
ON DURATION>4 DO STOP;
ON DURATION>2 DO SP ← 2*SP;
ENDM;
FINGER CONTROL
Each arm has two fingers at the end which are capable of
closing and opening at various speeds. The relevant reserved words
are OPENING, which is to be set to the desired (scalar) opening, and
VELOCITY, which is to be set to the speed desired. It is possible to
refer to the scalar variable SQUEEZE, which indicates the force being
applied by the fingers.
An example:
OPERATE FINGERS
WITH OPENING=4;
WITH VELOCITY=2;
ON SQUEEZE > 3 DO STOP;
ENDM;
WORLD MODEL SPECIFICATION
The world is a collection of all variables currently
declared, along with planning values and attachment structure. In
addition, atoms and their property lists are part of the world. We
will discuss how the world is affected by various statements and how
it is of use.
ASSERTIONS
The first way to affect the nature of the world is to make an
assertion. This tells the compiler that some planning value, or
range of planning values, obtains for a given variable. An example:
ASSERT X = 7, 0 < Y < 4, Z > 2;
The effect of this is to inform the compiler what the possible
planning values might be for the several variables. This set of
planning values will remain in effect until some statement is
executed which causes the planning values to change. For those
values which are specified as ranges, a medial planning value is
taken when needed.
It is difficult for the compiler to maintain unambiguous
planning values within the THEN and the ELSE parts of conditionals,
and especially difficult at the beginning of the next statement.
Therefore, during each branch, a separate world is in effect,
stemming from the world in force before the IF. All variables
modified in either branch have planning value "undefined" at the
close of the conditional; assertions must be used to inform the
compiler of any planning values it might need thereafter. Here is an
example:
IF G=1
THEN BEGIN
ATTACH FROB TO YELLOW;
MOVE FROB TO HOLE ENDM;
OPERATE YFINGERS WITH OPENING=5 ENDM;
MOVE YELLOW TO YPARK ENDM;
END;
ASSERT YELLOW=YPARK;
ASSIGNMENTS
The second way that the world changes is after every
assignment statement. The right-hand-side of the assignment is
evaluated using planning values, and the result is placed as the
planning value of the left hand side. Thus if the statement W ← X*Y
were to be executed immediately following the assertion shown above,
the planning value for W would become 0 < W < 28. Construction of
complex datatypes, like vectors, from scalars which have assertions
on them has the effect of carrying those assertions along as part of
the planning value of the left hand side.
In this context, any motion statement is like an assignment
to the hand's value. The planning effect of MOVE YELLOW TO F1 is
that the planning value of the yellow hand becomes the planning value
of F1.
ATTACHMENT
The statement ATTACH F1 TO F2 creates a compile-time
structure which causes the planning vallue of F1 to be changed every
time the planning value of F2 changes. It is as if there were a rod
holding F1 to F2, so that motions of F2 are passed along. There may
be some confusion concerning the meaning of moving F1 when it is
attached to F2. Does this also move F2? The answer is that it does
not. If one would prefer that the attachment be "two-way", that is,
symmetric, then the attachment statement looks like this: ATTACH F1
TO F2 RIGIDLY. If one expects to want to be able to modify the
relation between F1 and F2 without specifying which of them is to
move, then one further complication is added: ATTACH F1 TO F2
(RIGIDLY) BY T1. Here, T1 is the name of a trans, which will be set
to F2→F1. The statement DETACH F1 releases the attachment.
GRAPH-STRUCTURE BUILDING
Attachments are stored in both the compiler and the runtime
as a graph structure. The nature of this structure is described
later, as are the algorithms which serve to extract values from a
graph and insert new values into it. Suffice it here to say that if a
value is marked as invalid, then a calculator is called to try to
form a valid value; if it fails, then the current (invalid) value is
returned as a provisional answer. When a value is inserted into the
structure, all those values whose calculators depend on the new value
are marked as invalid, so that the next time they are needed, graph
searching is performed. Building a graph structure therefore involves
specifing the calculator for all variables. This is done as follows:
A <= B*C {B,C} has the effect of placing as the calculator of A the
expression B*C. The list in curly brackets is the DEPENDENCY list; it
implies that if either B or C changes, then A is to be marked as
invalid. The equivalent of ATTACH F1 TO F2 BY T1 is this:
T1 ← F2 → F1;
F1 <= F2 * T1 {F2, T1};
T1 <= F2 → F1 {F1};
In addition to the calculator, each variable in a graph has a CHANGER
associated with it. The changer is a set of instructions to be
executed in order to make a new assignment to the value of that
variable. It has access to the old value of the cell (called OLD),
and the new value which is to be put there. The changer is the last
procedure called in the modification of the value of a cell. If no
changer is specified for a variable V, then the default changer is V
← NEW. If the user wishes to place some other changer in a cell,
this can be done using the "<≡" construct. Thus, the default is:
T1 <≡ (T1 ← NEW);
One way to attach F1 to F2 is the following:
F2 <≡ BEGIN
F1 ← F2*(OLD→F1);
F2 ← NEW;
END;
SAVING AND RESTORING
The statement SAVE WORLD IN W1 will cause all the world at
that point in the planning to be written out into a file called
W1.WLD. The statement RESTORE WORLD FROM W1 will read in this file
and set up the world as it was when saved. This is particularly
useful for recovering when the arm runs into trouble; it makes it
unnecessary to begin the planning from scratch. It is also possible
to improve the planning values of frames after a period of execution;
this is done by the statement RESTORE WORLD FROM RUNTIME.
USES OF THE WORLD MODEL
The world model is used for several purposes: 1) to allow
trajectories to be calculated at compile time. 2) to allow the
expander to conditionally expand library routines.
CONDITIONAL EXPANSION
The way to query the state of the world is with the IFW construct.
For example, in order to write some code to bring the arm to park only
if it is not already there, on can say:
IFW BLUE ≠ BPARK THENW
MOVE BLUE TO BPARK ENDM;
This is especially useful in interfacing library routines with the
programs which call them. The values used in the booleans of
conditional expansions are always planning values. The values
of properties are also accessible to the conditionals.
OVERVIEW OF THE RUNTIME
The runtime is a set of programs residing in the PDP-11.
We will discuss control structures and data structures.
CONTROL STRUCTURES
PROCESS TYPES
There are several types of processes any number of which can
be active at any time:
1) Interpreters
2) Joint servos
3) On-monitors
An INTERPRETER is a process which is executing arithmetic or
other stack-oriented instructions, not one of the moves. As soon as
it encounters a move, it instantiates the required joint servos and
on-condition checkers and waits for the termination of the move
before continuing. Each interpreter also has a reserved cell in
which it stores information on where it currently is in the source
code; this is useful for debugging.
A JOINT SERVO is a process whose task is to servo one joint
of a moving arm, according to the planned trajectory for that joint.
When finished, the servo stops the joint and disappears. If the
joint should be stopped by some other process, the servo cleans up
the mess and dismisses.
An ON-MONITOR is a process which continually checks for some
condition. If that condition should appear, then those actions
specified by the compiler as critical are done immediately (in a
non-interruptable fashion); for the rest, the monitor sprouts an
interpreter. The ON-monitor can be in two states: enabled and
disabled. The checking is only done while the monitor is enabled.
The monitor disappears only when the system kills it.
INTERPRETABLE CODE
The basic instruction emitted by the compiler is one 16-bit
word. The first 8 bits are the opcode, and the last 8 are used to
form the operand address, if the opcode needs one. Addressing modes
are either immediate, in which case the next word has the address, or
relative (to the program counter). Immediate addressing is indicated
by the second byte being 0. Anything else is relative addressing;
bit 8 (the lefthand bit of the righthand byte) is a sign bit; thus
one can look 127 locations forward or backward; the full word address
will be found at this place. Full-word adresses can be indirect;
this is indicated by a high-order bit (ie, bit 0) being 1.
Indirection can proceed to any level.
STACK OPERATORS
pushadr <arg> puts <arg> on top of the stack. It is assumed that
<arg> is the address of a variable.
pushval <arg> puts value of variable pointed to by <arg> on stack.
gets good value, if necessary.
pop pops the stack.
copy <num> finds the <num>'th element down in the stack, and copies
it to the top.
flush clears the stack.
store <arg> pointer at top of stack copied into value pointer at <arg>;
stack is popped.
SINGLE FRAME OPERATIONS
solve takes a pointer to a frame value cell from top of stack.
Generates arm solution (if necessary) and stores in the
value cell. The stack is popped.
invert the inverse of the value cell at top of stack goes to
top of stack; old top popped.
ARITHMETIC
For the following, the args are on the stack, are popped
after the operation, the answer pointed to on top of stack. Earlier
arguments deeper on the stack.
s+s scalar addition. 2 args.
s-s scalar subtraction. 2 args.
s*s scalar multiplication. 2. args.
s/s scalar division. error if second arg is 0. 2 args.
|v| magnitude of vector. 1 arg.
v.v dot product. returns scalar.
(sss) forms vector from 3 scalars. 3 args.
s*v dilation of vector. 2 args. scalar first.
v+v vector addition. 2 args.
v∂v vector rotated by vector. second arg is rotation. 2 args.
t*v transformation of vector. trans first. 2 args.
[v:v] forms frame from 2 vectors. first is loc, second orient. 2 args.
f+v translation of frame. 2 args. frame first.
f∂v rotation of frame. 2 args. frame first.
t*f transformation of frame. 2 args. frame first.
f→f forms trans from two frames. 2 args. f1'f2.
[v|v] forms trans from two vectors. 1: trans; 2: rot.
t+v translates trans. 2 args. trans first.
t∂v rotates trans. 2 args. trans first.
t*t composition (to the left) of two transes.
tinv inverse of trans
EXTRACTION AND COMPOSITION
loc location of frame replaces it at top of stack.
orient orientation of frame replaces it at top of stack.
xscal x coordinate of vector replaces it at top of stack.
yscal y coordinate of vector replaces it at top of stack.
zscal z coordinate of vector replaces it at top of stack.
INSTANTIATION, DESUBSTATIATION, AND TRANSSUBSTANTIATION
sprouti <arg> start up an interpreter with name <arg>. The location
of its block of code is on the stack; pop it.
sprouto <arg> start up an on-monitor with name <arg>. The location
of its block of code is on the stack; pop it.
enable <arg> the on-monitor with name <arg> is enabled.
disable <arg> the on-monitor with name <arg> is disabled.
delayme wait until all descendent (non on-monitor) processes are dead.
Then kill descendent on-monitors and continue.
die terminate this process. Automatically first calls "delayme".
JUMPS
These have not yet been written.
nop no-op.
ARM AND DEVICE CONTROL
move <arg> <arg> points to the move vector.
go <arg> <arg> point to the GO table.
search <arg> <arg> points to the search vector.
stop <arg> <arg> encoding of what devices must be stopped.
INPUT AND OUTPUT
Some sort of I/O will be implemented, most likely including string
output to the supervisor, error message output, and input (from supervisor
or from coresident routines) of value cells.
DEBUGGING AIDS
source <arg> notes that <arg> is where the interpreter is now in
source code.
tellsource output current source location to the 10.
step begins step mode, which does one interpretation at a time,
requires message to continue.
offstep turns off step mode; normal speed is resumed.
DATA STRUCTURES
VALUE CELLS
Each variable has a value cell, either associated with it
directly or pointed to by the graph structure. Each datatype has its
own format for the value cell. Fixed-point numbers are used
throughout.
Scalars are stored in a single word, in fixed-point format.
Vectors are stored in four consecutive words. The fourth
entry is usually 1; the arithmetic routines are optimised for such
normalised vectors. To normalise a vector, divide each entry by the
fourth one.
Planes are also stored in four words. The first three
represent an outward-facing normal, and the last is the negative
distance to the (table) origin.
Frames are stored as 4x4 arrays, by columns. This includes
only the O, A, and P columns of the 4x4 array. In addition to the 9
matrix positions, there are 6 words set aside for the joint angles
associated with the frame, and one validity bit to signal the
correctness of those joint angles. They are calculated only if
needed. This happens if the frame is being used as a point in a
trajectory. A validity bit is associated with the joint angles; it is
made true when they are calculated, and false when the 4x4 part of
the frame changes.
Transes are stored in two 4x4 arrays: One is the same as the
format for frames, and the other is the inverse.
GRAPH STRUCTURES
Those variables participating in the graph structures have a
special node cell.
NODE CELL
invmark -- =0 if value is valid, otherwise invalid (note: the
evalnode algorithm uses a "time" to detect cycles. Therefore, this
field needs to be (at least) 16 bits.
value -- pointer to a value cell.
calculator -- points to a list of calculator cells
changer -- points to a block of interpretable code. There are
a few special-purpose changers which do not point to any code, but
are used as shorthands. These include "VALUE ← NEW".
dependents -- points to a list of dependents
type -- encoding (in several bits) of datatype.
CALCULATOR CELL
link -- link to next on the chain (there can be more than one
calculator for a node).
needed -- points to list of variables needed for this
calculator. The dependents cell format is used for the needed list.
code -- points to a block of interpretable code.
DEPENDENTS CELL
link -- link to next on the chain (there can be more than one
dependent of a node).
dep -- points to the node cell of one dependent.
ALGORITHMS FOR USE OF GRAPH STRUCTURE
PROCEDURE invalidate (POINTER(NODE) n);
IF invmark(n)=0 THEN
BEGIN COMMENT: This cell currently marked valid;
POINTER p;
invmark(n)← -1;
p ← dependents(n);
WHILE p≠NULL DO
BEGIN COMMENT: Mark all dependents as invalid;
invalidate(p);
p ← link(p)
END
END;
PROCEDURE change (POINTER(NODE) n; POINTER(VALUE) vnew);
BEGIN
POINTER(VALUE) vold;
invalidate(n);
vold ← value(n);
value(n)←vnew;
p ← changer(n);
WHILE p≠NULL DO
BEGIN COMMENT: Handle all changers;
APPLY(code(p),vold,vnew);
p ← link(p);
END;
invmark(n) ← 0;
END;
POINTER(VALUE) PROCEDURE getvalue (POINTER(NODE) n);
BEGIN
IF invmark(n)≠0 THEN evalnode(n, time ← time+1);
RETURN(value(n));
END;
PROCEDURE evalnode (POINTER(NODE) n, INTEGER t);
BEGIN COMMENT: Put a good value in the value cell of n.
t is used to break cycles;
IF invmark(n)=0 ∨ invmark(n)=t THEN RETURN;
invmark(n) ← t;
p ← calculator(n);
WHILE p ≠ NULL DO
BEGIN "cloop"
POINTER(dependent) d;
d ← needed(p);
WHILE d ≠ NULL DO
BEGIN
evalnode(dep(d),t);
IF invmark(dep(d))≠0 THEN
BEGIN
p ← next(p);
CONTINUE "cloop";
END;
d ← next(d);
END;
value(n)←APPLY(code(p), args(p));
invmark(n)←0;
RETURN;
END;
END;
TRAJECTORIES not yet ready for perusal
1) Code is executed interpretatively to set up temporary frames
necessary for this motion.
2) The "start move" pseudo-op is encountered; it points to the
location of a vector of joint start addresses (for 6 joints, need a
vector of 12 adresses, because each joint needs both its location and
its inertia tables).
3) A scan is made for each joint down its chain of location tables,
during which the coefficients for each segment are modified by a 5th
order polynomial to bring them into conformity with the frames
specified, if necessary.
4) A process is sprouted for each joint which will service that
joint. Actually, only one copy of that process exists, and each
joint has its own data area which contains a) servo constants for
that joint, b) location counters into the two types of tables, c)
precalculated values relevant to the next awakening.
5) Each process, on each awakening, checks the clock to make sure it
was awakened at the right time (fatal error otherwise), outputs the
precalculated drive, decides how long it is willing to sleep,
reserves an awakening slot (more on these soon) in the calendar,
computes the drive for that time, and goes to sleep.
6) As each joint finishes its whole trajectory, it requests that the
monitor kill it. When all the joints have been killed, the monitor
(which knows that a move was in progress) returns control to the
interpreter (which is itself a process) where it left off.
Termination of a move is quite simple: The joint status word, which
is global to the entire runtime, is just set for each joint affected
to a value which means "unrunnable" The next time the servo is
awakened, it will notice this and request euthanasia. The
termination also requires that the motors be stopped, and the brakes
applied, and the resting point of the arm determined.
Some care must be taken to prevent two interpreters proceeding at the
same time under conditions whereby one should really be waiting for
the other. Specifically, during a move, the interpreter that
initiated that move is suspended until it is complete. Therefore, if
an on-test causes another interpreter to start, the suspended
interpreter must remain suspended until the new one dies.
TRAJECTORY TABLES
The following are necessary properties of trajectory tables:
Must state which frames are used, so the servo can do appropriate
update.
Must be perspicuous enough to allow servo to find the things which
it must update.
Must allow escape to interpret mode at end of each segment for
each joint, in order to initiate new motions or "on" tests.
A trajectory table is a set of joint-segment tables. Each
joint-segment table is intended to give instructions for the servoing
of one joint along one segment of the path. There are two types of
such tables: location and inertia. The servo follows each of these
simultaneously and asynchronously.
FORMAT OF THE LOCATION-JOINT-SEGMENT TABLE: This table is ten words
long.
words 1,2,3,4,5,6: coefficients a5,a4,a3,a2,a1,a0 of the trajectory.
Polynomial is normalised for tε[0,1].
word 7: Duration of segment in milliseconds.
word 8: Pointer to next location-joint-segment table for this joint.
If this is the last segment, word 8 is 0.
word 9: Pointer to frame which is to be assumed at end of this
segment. If no particular frame, then this is 0. This is used in a
preprocessing step to modify the coefficients of the polynomial; at
swing time it is not needed.
word 10: If not 0, then a pointer to a location of interpretable
code where an interpreter is to be instantiated and begun. This is
for the THEN part of VIA lists.
FORMAT OF THE INTERTIA-JOINT-SEGMENT TABLE: This table is 7 words
long.
words 1,2: Coefficients j1,j0 of joint inertia polynomial, normalized
for tε[0,1].
words 3,4: Coefficients g1,g0 of gravity loading polynomial.
Likewise normalized.
word 5: Duration of segment in milliseconds.
word 6: Control word, with bits for free, force, drive, nodrive, etc.
see later discussion on control words. This is copied into a global
location at start of inertia-joint-segment.
word 7: Pointer to next intertia-joint-segment table for this joint.
If this is the last segment, word 7 is 0.
GO TABLES
The following are necessary properties of go tables:
Must state list of frames to use (including initial deproach
and via-list)
Must allow escape to interpret mode at end of each segment.
A GO table is a list of frames through which the motion is to
proceed. Each is specified by its address. The first one is the deproach
of the start frame; the penultimate is the deproach of the final
frame. Following each frame address is an interpreter address, which
is the adrress of the interpreter (if any) to be invoked upon achievement
of the preceeding frame. The last frame is distinguished by an interpreter
address of -1.